In multicast/broadcast applications, data are transmitted from a server to multiple receivers over wired and/or wireless networks. Herein, a “/” is used to indicate alternative names for the same or similar components. A multicast system as used herein is a system in which a server transmits the same data to multiple receivers simultaneously, where the receivers form a subset of all the receivers up to and including all of the receivers. A broadcast system is a system in which a server transmits the same data to all of the receivers simultaneously. That is, a multicast system by definition can include a broadcast system.
Some concepts/terms that may benefit the understanding of the present invention are provided. A frame is a unit of data. That is, data can be packaged in packets or frames or any other convenient format. As used herein a frame is used to indicate data packaged in a format for transmission.
The minimum multipoint relay set problem has been proved to be NP complete, which means there are no polynomial methods to solve the problem. In one prior art article a heuristic algorithm was proposed to solve the MPR problem. In this heuristic algorithm, first those one hop neighbors that are the only neighbor of some two hop neighbor nodes are added to the MPR set. The heuristic algorithm then finds the one hop neighbor node that covers the maximum uncovered two hop neighbor nodes and adds this node to the MPR set. This continues until all the two hop neighbor nodes are covered. Recently, the concept of MPR has also been introduced in a reactive Mobile Ad Hoc Network (MANET) routing protocol and a new IETF draft for message flooding in MANET networks.
It should be noted that in wireless networks, the number of one-hop and two-hop neighbor nodes of a node often is not very big. In this case, it is still viable to find the minimum MPR set using an optimized approach.
The present invention solves these and other problems by describing both an optimized and a heuristic method to perform minimum MPR set selection. Multicast channel reservation in WLAN is also a challenging problem, especially in OBSSs. In earlier applications PCT/US08/008162 filed Jun. 30, 2008, Applicants described using bit-mapped Request-to-Send/Clear-to-Send (RTS/CTS) signaling for multicast channel reservation in OBSSs in wireless networks. The present invention uses the selected minimum MPR set to improve the scalability in OBSSs in wireless networks including wireless local area networks (WLANs).